package com.cb2.algorithm.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * <a href="https://leetcode.cn/problems/linked-list-components">链表组件(Linked List Components)</a>
 * <p>给定链表头结点 head，该链表上的每个结点都有一个 唯一的整型值 。同时给定列表 nums，该列表是上述链表中整型值的一个子集。</p>
 * <p>返回列表 nums 中组件的个数，这里对组件的定义为：链表中一段最长连续结点的值（该值必须在列表 nums 中）构成的集合。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入: head = [0,1,2,3], nums = [0,1,3]
 *      输出: 2
 *      解释: 链表中,0 和 1 是相连接的，且 nums 中不包含 2，所以 [0, 1] 是 nums 的一个组件，同理 [3] 也是一个组件，故返回 2。
 *
 * 示例 2：
 *      输入: head = [0,1,2,3,4], nums = [0,3,1,4]
 *      输出: 2
 *      解释: 链表中，0 和 1 是相连接的，3 和 4 是相连接的，所以 [0, 1] 和 [3, 4] 是两个组件，故返回 2。
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>链表中节点数为n</li>
 *     <li>1 <= n <= 10^4</li>
 *     <li>0 <= Node.val < n</li>
 *     <li>Node.val 中所有值 不同</li>
 *     <li>1 <= nums.length <= n</li>
 *     <li>0 <= nums[i] < n</li>
 *     <li>nums 中所有值 不同</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/10 11:06
 */
public class LC0817LinkedListComponents_M {

    static class Solution {
        public int numComponents(ListNode head, int[] nums) {
            Set<Integer> set = new HashSet<>();
            for (int num : nums) {
                set.add(num);
            }
            int componentCount = 0;
            while (head != null) {
                if (set.contains(head.val)) {
                    ++componentCount;
                    while (head != null && set.contains(head.val)) {
                        head = head.next;
                    }
                } else {
                    head = head.next;
                }
            }
            return componentCount;
        }
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(0);
        head.next = new ListNode(1);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(3);

        Solution solution = new Solution();
        System.out.println(solution.numComponents(head, new int[]{0, 1, 3}));
        head.next.next.next.next = new ListNode(4);
        System.out.println(solution.numComponents(head, new int[]{0, 3, 1, 4}));
    }
}